from typing import List


class Solution:
    def strStr(self, s: str, t: str) -> int:
        def z_table(s: str) -> List[int]:
            n = len(s)
            z = [0] * n
            z[0] = n
            i, last, r = 1, 1, 1
            while i < n:
                critical_point = i - last
                length = min(z[critical_point], r - i) if r > i else 0
                while i + length < n and s[i + length] == s[length]:
                    length += 1
                if i + length > r:
                    last, r = i, i + length
                z[i] = length
                i += 1
            return z

        def e_table(s1: str, s2: str) -> List[int]:
            m, n = len(s1), len(s2)
            e = [0] * m
            z = z_table(s2)
            i, last, r = 0, 0, 0
            while i < m:
                critical_point = i - last
                length = min(z[critical_point], r - i) if r > i else 0
                while i + length < m and length < n and s1[i + length] == s2[length]:
                    length += 1
                if i + length > r:
                    last, r = i, i + length
                e[i] = length
                i += 1
            return e

        def kmp(s1, s2):
            e = e_table(s1, s2)
            n = len(s2)
            for i, length in enumerate(e):
                if length == n:
                    return i
            return -1
        return kmp(s, t)